

# include <iostream>


# include <tpl_dynBinHeap.H>
# include <tpl_dynListQueue.H>
# include <tpl_concurrent_graph.H>
# include <tpl_graph.H>
# include <tpl_graph_utils.H>
# include <kruskal.H>
# include <prim.H>
# include <dijkstra.H>

# define INDENT "    "

using namespace Aleph;

struct Ciudad 
{
  enum Tipo_Ciudad { CAPITAL, CIUDAD, PUEBLO, CASERIO, CRUZ, DESCONOCIDO };

  string nombre;

  Tipo_Ciudad tipo;

  Ciudad() : tipo(DESCONOCIDO) { /* empty */ }

  Ciudad(char * nom) : nombre(nom), tipo(DESCONOCIDO) { /* empty */ }

  Ciudad(const string& str) : nombre(str), tipo(DESCONOCIDO) { /* empty */ }

  bool operator == (const Ciudad & c) const
  {
    return strcasecmp(c.nombre.c_str(), nombre.c_str()) == 0;
  }
};

struct Via
{ 
  enum Tipo_Via { AUTOPISTA, CARRETERA1, CARRETERA2, CARRETERA3, GRANZON,
		  CHALANA, DESCONOCIDO };

  string nombre;
  int distancia; 
  Tipo_Via tipo;

  Via() : tipo(DESCONOCIDO) {}

  Via(int d) 
    : nombre("Desconocido"), distancia(d), tipo(DESCONOCIDO) { /* empty */ }

  Via(char * nom, int d) 
    : nombre(nom), distancia(d), tipo(DESCONOCIDO) { /* empty */ }

  Via(const string& nom, int d) 
    : nombre(nom), distancia(d), tipo(DESCONOCIDO) { /* empty */ }

  typedef int Distance_Type;

  Distance_Type& get_distance() { return distancia; }

  static const Distance_Type Zero_Distance = 0;
};

typedef Concurrent_Node<Ciudad> Nodo;
typedef Concurrent_Arc<Via> Arco;
typedef Concurrent_Graph<Nodo, Arco> Mapa;

//typedef List_Digraph<Ciudad, Via> Dimapa;

//typedef Mat_Graph< List_Graph<Ciudad, Via> > Mat_Mapa;

//typedef Ady_Mat<Mat_Mapa, int> Dist_Mat;

struct Comparar_Vias
{
      bool 
  operator () (const Via::Distance_Type & d1, const Via::Distance_Type & d2)
  {
    return d1 < d2;
  }
};

struct Sumar_Vias
{
  Via::Distance_Type operator () (const Via::Distance_Type & d1, 
				  const Via::Distance_Type & d2)
  {
    return d1 + d2;
  }
};

void visitar(Mapa & g, Mapa::Node * node, Mapa::Arc * arc)
{
  cout << "Estoy en  " << node->get_info().nombre << " viniendo desde " 
       << (arc not_eq NULL ? g.get_connected_node(arc, node)->get_info().nombre : "NULO") 
       << endl ;
}

void insert_via(Mapa& mapa, 
		const string & c1, const string & c2,
		int distancia)
{
  Mapa::Node * n1 = mapa.search_node(Ciudad(c1));

  if (n1 == NULL)
    n1 = mapa.insert_node(c1);

  Mapa::Node * n2 = mapa.search_node(Ciudad(c2));

  if (n2 == NULL)
    n2 = mapa.insert_node(c2);

  string nombre_arco = n1->get_info().nombre + "--" + n2->get_info().nombre;

  mapa.insert_arc(n1, n2, Via(nombre_arco, distancia));
}


void imprimir_camino(Mapa::Path& path)
{
  cout << endl
       << "Camino: ";
  for (Mapa::Path::Iterator itor(path); itor.has_current(); itor.next())
    cout << itor.get_current_node()->get_info().nombre << "-";

  cout << endl;
}


void imprimir_mapa(Mapa & g)
{
  cout << endl
       << "Listado de nodos (" << g.get_num_nodes() << ")" << endl;

  for (Mapa::Node_Iterator node_itor(g); node_itor.has_current(); 
       node_itor.next())
    cout << INDENT << node_itor.get_current_node()->get_info().nombre << endl;

  cout << endl
       << endl
       << "Listado de arcos (" << g.get_num_arcs() << ")"
       << endl;

  for (Mapa::Arc_Iterator arc_itor(g); arc_itor.has_current();
       arc_itor.next())
    {
      Mapa::Arc * arc = arc_itor.get_current_arc();
      cout << arc->get_info().nombre << " " << arc->get_info().distancia << " de " 
	   << g.get_src_node(arc)->get_info().nombre << " a " 
	   << g.get_tgt_node(arc)->get_info().nombre << endl;
    }

  cout << endl
       << endl
       << "Listado del grafo por nodos y en cada nodo por arcos" 
       << endl;
   for (Mapa::Node_Iterator node_itor(g); node_itor.has_current(); 
       node_itor.next())
    {
      Mapa::Node * src_node = node_itor.get_current_node();
      cout << src_node->get_info().nombre << endl;
      for (Mapa::Node_Arc_Iterator itor(node_itor.get_current_node());
	   itor.has_current(); itor.next())
	{
	  Mapa::Arc * arc = itor.get_current_arc();
	  cout << INDENT << arc->get_info().distancia << " " 
	       << g.get_connected_node(arc, src_node)->get_info().nombre << endl;
	}
    }
  cout << endl;
}

void construir_mapa(Mapa& g)
{
  insert_via(g, "San Cristobal", "La Fria", 69);
  insert_via(g, "San Cristobal", "Sacramento", 113);
  insert_via(g, "San Cristobal", "San Antonio", 36);
  insert_via(g, "San Cristobal", "Rubio", 22);
  insert_via(g, "Rubio", "San Antonio", 48);
  insert_via(g, "Rubio", "Caparo", 150);
  insert_via(g, "Sacramento", "El Canton", 38);
  insert_via(g, "La Fria", "El Vigia", 86);
  insert_via(g, "El Vigia", "Santa Barbara", 59);
  insert_via(g, "El Vigia", "Merida", 79);
  insert_via(g, "La Fria", "Machiques", 252);
  insert_via(g, "Machiques", "Maracaibo", 130);
  insert_via(g, "Machiques", "Santa Barbara", 295);
  insert_via(g, "Maracaibo", "Paraguaipos", 55);
  insert_via(g, "Maracaibo", "Coro", 254);
  insert_via(g, "Maracaibo", "Valera", 201);
  insert_via(g, "Valera", "Merida", 167);
  insert_via(g, "Valera", "Carora", 120);
  insert_via(g, "Carora", "Barquisimeto", 102);
  insert_via(g, "Merida", "Barinas", 180);
  insert_via(g, "Barinas", "Caparo", 200);
  insert_via(g, "Barinas", "Guanare", 94);
  insert_via(g, "Caracas", "Barcelona", 310);
  insert_via(g, "Caracas", "San Juan", 139);
  insert_via(g, "Guanare", "Barquisimeto", 170);
  insert_via(g, "Barquisimeto", "San Fernando", 526);
  insert_via(g, "Barinas", "San Fernando", 547);
  insert_via(g, "Caparo", "San Cristobal", 201);
  insert_via(g, "Coro", "Valencia", 252);
  insert_via(g, "Valencia", "Barquisimeto", 220);
  insert_via(g, "Valencia", "Maracay", 49);
  insert_via(g, "Valencia", "San Carlos", 100);
  insert_via(g, "Maracay", "Caracas", 109);
  insert_via(g, "San Felipe", "Maracay", 315);
  insert_via(g, "San Felipe", "San Carlos", 241);
  insert_via(g, "San Felipe", "Barquisimeto", 86);
  insert_via(g, "San Felipe", "San Juan", 222);
  insert_via(g, "Guanare", "San Carlos", 173);
  insert_via(g, "San Juan", "San Fernando", 261);
  insert_via(g, "Barcelona", "Pto La Cruz", 10);
  insert_via(g, "Pto La Cruz", "Cumana", 82);
  insert_via(g, "Cumana", "Maturin", 199);
  insert_via(g, "Pto Ordaz", "Maturin", 171);
  insert_via(g, "Pto Ordaz", "Ciudad Bolivar", 107);
  insert_via(g, "El Tigre", "Ciudad Bolivar", 130);
  insert_via(g, "El Tigre", "Barcelona", 166);
  insert_via(g, "El Tigre", "San Juan", 435);
}



void via_a_distancia(Mapa::Arc * arc, int & distancia)
{
  if (arc != NULL)
    distancia = arc->get_info().get_distance();
};


int main()
{
  Mapa *g = new Mapa();

  construir_mapa(*g);

   cout << "Recorrido en profundidad " << endl;
  depth_first_traversal(*g, visitar);
  cout << endl;

//   cout << "Recorrido en amplitud " << endl;
//   breadth_first_traversal(g, visitar);
//   cout << endl;

  if (test_connectivity(*g))
    cout << "El grafo es conectado";
  else
    cout << "El grafo no es conectado";
  cout << endl;

  if (test_cycle(*g, g->search_node("San Cristobal")))
    cout << "Hay un ciclo desde San Cristobal" << endl;
  else
    cout << "No hay un ciclo desde San Cristobal" << endl;

  if (is_acyclique(*g))
    cout << "El grafo es aciclico (es un arbol)" << endl;
  else
    cout << "El grafo tiene ciclos" << endl;

  if (test_path(*g, g->search_node("El Vigia"), g->search_node("Carora")))
    cout << "Existe un camino desde El Vigia hacia Carora" << endl;


  Mapa::Path path(*g);
  find_path(*g, g->search_node("El Vigia"), g->search_node("Carora"), path);
  imprimir_camino(path);

  imprimir_mapa(*g);

  Mapa tree;
  spanning_tree<Mapa>(*g, tree);
  cout << endl
       << "Arbol abarcador " << endl;
  imprimir_mapa(tree);


  Mapa tree1;
  kruskal_min_spanning_tree<Mapa>(*g, tree1);
  cout << endl
       << "Arbol abarcador segun Kruskal" << endl;
  imprimir_mapa(tree1);

  Mapa tree2;
  prim_min_spanning_tree<Mapa>(*g, tree2);
  cout << endl
       << "Arbol abarcador segun Prim" << endl;
  imprimir_mapa(tree2);


  Mapa tree3;

  dijkstra_min_spanning_tree(*g, g->get_first_node(), tree3);
  cout << endl
       << "Arbol abarcador segun Dijkstra" << endl;
  imprimir_mapa(tree3);

  Mapa::Path min_path(tree3);
  if (find_path(tree3, tree3.get_first_node(), tree3.search_node("Carora"), 
		min_path))
    {
      cout << "Camino encontrado en Dijkstra: " 
	   << tree3.get_first_node()->get_info().nombre << " - Carora" << endl;
      imprimir_camino(min_path);
      cout << endl << endl;
    }
  else
    EXIT("Error no se encontr� camino!");

  Mapa::Path aux_path = min_path;

  min_path = aux_path;

  DynDlist<Mapa::Path> test;

  Mapa::Path path2(*g);
  dijkstra_min_path(*g, g->search_node("Guanare"),
		    g->search_node("San Fernando"), path2);

  cout << "Camino encontrado:" << endl;
  imprimir_camino(path2);
  cout << endl << endl;
  
# ifdef nada
  Mat_Mapa matriz(g);

  Ady_Mat<Mat_Mapa, int> distancias1(matriz, &via_a_distancia);

  Ady_Mat<Mat_Mapa, int> distancias2(distancias1);

  Mapa gc1 = g;

  Mapa gc2;

  gc2 = g;

  g = gc1;

  imprimir_mapa(g);

  //Dimapa dimapa;

  //gc2 = dimapa;

  EXIT("");

# endif
 	delete g;
}


